/*
 * @lc app=leetcode.cn id=525 lang=cpp
 *
 * [525] 连续数组
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        
        // see 0 as -1, same 0 and 1 means => sum = 0
        std::vector<int> prefixSum(n, 0);

        int sum = 0;
        for (int i=0;i<n;++i){
            if (nums[i] == 0){
                sum -= 1;
            }else{
                sum += 1;
            }

            prefixSum[i] = sum;
        }

        // <sum, the first index of this sum> 
        std::unordered_map<int, int> sumHash;
        sumHash.emplace(0, -1);
        int maxDis = 0;

        for (int i=0;i<n;++i){
            int currentSum = prefixSum[i];
            auto iter = sumHash.find(currentSum);
            if (iter != sumHash.end()){
                int currentDis = i - iter->second;
                if (currentDis > maxDis){maxDis = currentDis;}
            }else{
                sumHash.emplace(currentSum, i);
            }
        }

        return maxDis;
    }
};
// @lc code=end

// [0,1,0,1,1,1,0,0,1,1,
//  0,1,1,1,1,1,1,0,1,1,
//  0,1,1,0,0,0,1,0,1,0,
//  0,1,0,1,1,1,1,1,1,0,
//  0,0,0,1,0,0,0,1,1,1,
//  0,1,0,0,1,1,1,1,1,0,
//  0,1,1,1,1,0,0,1,0,1,
//  1,0,0,0,0,0,0,1,0,1,
//  0,1,1,0,0,1,1,0,1,1,
//  1,1,0,1,1,0,0,0,1,1]

int main(){
    std::vector<int> num = {
 0,1,0,1,1,1,0,0,1,1,
 0,1,1,1,1,1,1,0,1,1,
 0,1,1,0,0,0,1,0,1,0,
 0,1,0,1,1,1,1,1,1,0,
 0,0,0,1,0,0,0,1,1,1,
 0,1,0,0,1,1,1,1,1,0,
 0,1,1,1,1,0,0,1,0,1,
 1,0,0,0,0,0,0,1,0,1,
 0,1,1,0,0,1,1,0,1,1,
 1,1,0,1,1,0,0,0,1,1
    };
    Solution test;
    test.findMaxLength(num);
}

// [0,1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,0,1,1,0,1,1,0,0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,0,1,1,1,0,1,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,1,0,1,1,1,1,0,1,1,0,0,0,1,1]

    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        
        std::vector<int> prefixOne(n, 0);
        std::vector<int> prefixZero(n, 0);

        int counterOne = 0, counterZero = 0;
        for (int i=0;i<n;++i){
            if (nums[i] == 0){
                counterZero += 1;
            }else{
                counterOne += 1;
            }

            prefixOne[i] = counterOne;
            prefixZero[i] = counterZero;
        }

        int left = 0;
        int right = n-1;

        int zeroNum = prefixZero[right];
        int oneNum = prefixOne[right];

        while (zeroNum != oneNum and left < right){
            if (zeroNum > oneNum){
                // search zero to go middle
                if (nums[left] == 0){
                    left += 1;
                }else{
                    right -= 1;
                }
            }else{
                // too much 1, search one and remove it 
                if (nums[left] == 1){
                    left += 1;
                }else{
                    right -= 1;
                }
            }

            // todo left and right are all needed, the less
            ;

            // update 0 / 1 number
            if (left == 0){
                zeroNum = prefixZero[right];
                oneNum = prefixOne[right];
            }else{
                zeroNum = prefixZero[right] - prefixZero[left-1];
                oneNum = prefixOne[right] - prefixOne[left-1];
            }
        }

        int res = right - left + 1;

        // check if [0, 0]
        if (left == right){
            res = 0;
        }else{
            res = right - left + 1;
        }

        printf("%d %d\n", left, right);
        return res;
    }
